package pro1_10.pro9;

import java.util.Arrays;

/**
 * @author yaohuaiying
 * @create 2018-02-07 17:11
 *
 * 第9题
-----------------------------------
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
      8
    /  /
   6    10
  / /   / /
 5 7    9 11
因此返回true
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

 思路
 左 < 根 < 右
 根是最后一个输出
 找到第一个比根大的位置 那是根的右树的开始节点 从这里往后都比根大 往前比根小 以此把数组分开 继续递归
 长度 0 1 2 特殊对待……
 **/
public class Main {
    public static void main(String[] agrs){
//        int[] data = {5,7,6,9,11,10,8};
//        int[] data = {5,7,6,9,11};
//        int[] data = {7,4,6,5};
        int[] data = {};
        boolean isTree = isTree(data, 0, data.length);
        System.out.println(isTree);
    }

    public static boolean isTree(int[] data, int begin, int end){
        int length = data.length;
        if(length == 0){
            return  false;
        }
        if(length == 2 || length == 1){
            return true;
        }
        int i = begin;
        int j = end;
        int gen = data[end-1];
        while(i < j && data[i] < gen) {
            i++;
        }
        if(i < j-1) {
            for (int index = begin; index < i; index++) {
                if (data[index] > gen) {
                    return false;
                }
            }
            for (int index = i; index < end; index++) {
                if (data[index] < gen) {
                    return false;
                }
            }
            int[] zuoShu = Arrays.copyOfRange(data,begin,i);
            isTree(zuoShu,0,zuoShu.length);
            int[] youShu = Arrays.copyOfRange(data,i,end-1);
            isTree(youShu,0,youShu.length);
        }
        return  true;
    }
}
